#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include <immintrin.h>
#include <emmintrin.h>
#endif
#include <bits/stdc++.h>

#define int ll

#define rep(i, a, b) for(int i = (a), i##end = (b); i <= i##end; i++)
#define _rep(i, a, b) for(int i = (a), i##end = (b); i >= i##end; i--)
#define ec first
#define fb second
#define dl make_pair
#define dk(...) make_tuple(__VA_ARGS__)
#define de(val) cerr << #val << " = " << (val) << endl

using namespace std;

typedef long long ll;
typedef __int128 i128;
typedef pair <int, int> pii;

int read() {
	int x = 0, f = 1; char c = getchar();
	while (!isdigit(c)) {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c)) {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return x * f;
}

template <typename _Tp>
void print(_Tp x) {
	if (x < 0) x = (~x + 1), putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

int T, a, b, c;
const int MOD = 1e9 + 7;

int mylog(int a, int b) {
	return log(a) / log(b);
}

void solve() {
	int ans = 0;
	a = read(), b = read(), c = read();
	// ans = (min(min(a, b), c) + c - 1) % MOD;
	// cerr << ans << endl;
	rep (i, 2, min(a, (int) sqrt(b))) {
		ans = (ans + min(mylog(b, i) - 1, (c / i - 1))) % MOD;
	}
	// cerr << ans << endl;
	rep (i, 2, min(b, (int) sqrt(a))) {
		i128 val = i;
		int cnt = 1;
		while (1) {
			val = val * i;
			++cnt;
			if (val > cnt * c || val > a) break;
			if (val % cnt == 0 && val / cnt <= c) ans = (ans + 1) % MOD;
		}
		// cerr << "de:" << i << " " << ans << endl;
	}
	print(ans), puts("");
}

signed main() {
#ifndef LOCAL
#ifndef ONLINE_JUDGE
	freopen("alien.in", "r", stdin);
	freopen("alien.out", "w", stdout);
#endif
#endif
	T = read();
	while (T --> 0) solve();
	return 0;
}
